# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

headA=ListNode(4)
headB=ListNode(5)
headA.next=ListNode(1)
headB.next=ListNode(6)
headB.next.next=ListNode(1)
headC=ListNode(8)
headC.next=ListNode(4)
headC.next.next=ListNode(5)
headA.next.next=headC
headB.next.next.next=headC

def getIntersectionNode(headA, headB):
    nodeSet=set()
    while headA:
        nodeSet.add(headA)
        headA=headA.next
    while headB:
        if headB in nodeSet:
            return headB
        headB=headB.next
    return None
print(getIntersectionNode(headA,headB))
